// NC285 矩阵中的路径
// 判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param matrix char字符型vector<vector<>>
   * @param word string字符串
   * @return bool布尔型
   */
  bool hasPath(vector<vector<char>>& matrix, string word) {
    // write code here
    if (matrix.size() == 0 || word.length() == 0) {
      return false;
    }
    vector<vector<int>> dirs = {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0},
    };
    int width = matrix.size();
    int height = matrix[0].size();
    set<pair<int, int>> stVisited;
    queue<tuple<int, int, int>> quCell;
    vector<vector<int>> matLength(width, vector<int>(height, 0));
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (matrix[i][j] == word[0]) {
          quCell.push(make_tuple(i, j, 0));
          stVisited.insert({i, j});
        }
      }
    }

    while (!quCell.empty()) {
      //      auto ce = quCell.front(); quCell.pop();
      auto [i, j, pos] = quCell.front();
      quCell.pop();
      //      int i = get<0>(ce);
      //      int j = get<1>(ce);
      //      int pos = get<2>(ce);
      for (auto dir : dirs) {
        int x = dir[0] + i;
        int y = dir[1] + j;
        if (x < 0 || x >= width || y < 0 || y >= height ||
            stVisited.count({x, y}) > 0 || matrix[x][y] != word[pos + 1]) {
          continue;
        }
        stVisited.insert({x, y});
        quCell.push(make_tuple(x, y, pos + 1));
        matLength[x][y] = pos + 1;
        printf("push=%d,%d...%d.%c\n", x, y, pos + 1, matrix[x][y]);
      }
    }
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        printf("true = %d,%d,%d\n", i, j, matLength[i][j]);
        if (matrix[i][j] == word.back() &&
            matLength[i][j] == word.length() - 1) {
          return true;
        }
      }
    }
    printf("false\n");
    return false;
  }
};

int main_nc285() {
  Solution sol;
  vector<vector<char>> matrix;  // = {'a'};
  matrix.push_back(vector<char>{'A', 'B', 'C', 'E', 'H', 'J', 'I', 'G'});
  matrix.push_back(vector<char>{'S', 'F', 'C', 'S', 'L', 'O', 'P', 'Q'});
  matrix.push_back(vector<char>{'A', 'D', 'E', 'E', 'M', 'N', 'O', 'E'});
  matrix.push_back(vector<char>{'A', 'D', 'I', 'D', 'E', 'J', 'F', 'M'});
  matrix.push_back(vector<char>{'V', 'C', 'E', 'I', 'F', 'G', 'G', 'S'});
  string word = "SGGFIECVAASABCEHJIGQEM";
  bool bHas = sol.hasPath(matrix, word);
  printf("out=%d\n", bHas);
  return 0;
}
